#include<iostream>
#include<vector>
#include<math.h>
#include <string.h> 
#include <fstream>
using namespace std;
#define MAX 1000

struct Node
{
	char name[8], address[20];
	char num[12];
	bool isValid;
	bool empty;
	int conftimes;		// 记录探测次数 
};

void Gethash1(vector<Node> &hash, Node a[], int m, int n)//建立hash表，按号码
{
	hash.resize(m);//hash表长
	for (int i = 0; i < m; i++)
		hash[i].empty = true;
	int H;	
	for (int i = 0; i < n; i++)
	{
		int c = 3;
		unsigned int v = (int)a[i].num[2];		// 强制类型转换 unsigned使结果非负 
		while ( a[i].num[c] != '\0')			// 用来进行求和来处理冲突
		{
			v += (int)a[i].num[c];
			c++;
		}
		H = v % m;//hash函数为Hash(key)=key%p,p=m
		int ct = 1;
		while (!hash[H].empty)//线性探测法处理冲突
		{
			H = (H + 1) % m;
			ct++;
		}
		hash[H] = a[i];
		hash[H].empty = false;
		hash[H].conftimes = ct;
		hash[H].isValid = true;
	}
}

void Gethash2(vector<Node> &hash, Node a[], int m, int n)//建立hash表，按姓名
{
	hash.resize(m);//hash表长
	for (int i = 0; i < m; i++)
		hash[i].empty = true;
	int H;
	for (int i = 0; i < n; i++)
	{
		int c = 1;
		unsigned int v = (int)a[i].name[0];		// 强制类型转换 
		while (a[i].name[c] != '\0')			// 用来进行求和来处理冲突
		{
			v += (int)a[i].name[c];
			c++;
		}
		H = v % m;//hash函数为Hash(key)=key%p,p=m
		int ct = 1;
		while (!hash[H].empty)//线性探测法处理冲突，，若此位置已有数字则判断下一位  
		{
			H = (H + 1) % m;
			ct++;
		}
		hash[H] = a[i];
		hash[H].empty = false;
		hash[H].conftimes = ct;
		hash[H].isValid = true;
	}
}

int HashSearch1(vector<Node> hash, int m, char num[12])//对应以线性探测法处理冲突建立的hash表（按号码）的查找
{
	int c = 3;
	unsigned int v = (int)num[2];
	while (num[c] != '\0')
	{
		v += (int)num[c];
		c++;
	}
	int pos = v%m;
	int t = pos;
	while (hash[pos].isValid && !hash[pos].empty)			// 分两种情况，当此位置有效且不为空 
	{
		if (strcmp(num, hash[pos].num) == 0)				// 通过判断此位置的号码是否与所找号码相等来判断是否此为要查找的信息 
		{
			cout << hash[pos].name << " " << hash[pos].address << " " << hash[pos].num << endl;
			return pos;
		}			
		else						// 若不相等则找下一位再接着进行判断 
			pos = (pos + 1) % m;
		if (pos == t)					// 若找到完所有的有信息位置依旧没有，说明没有此信息记录
		{
			cout << "无此记录" << endl;
			return -1;
		}
			
	}
	cout << "无此记录" << endl;				//若线性探测找到空位置却没有查找到所找信息，也说明无此信息记录 
	return -1;
}

int HashSearch2(vector<Node> hash, int m, char name[8])//对应以线性探测法处理冲突建立的hash表（按姓名）的查找
{
	int c = 1;
	unsigned int v = (int)name[0];
	while (name[c] != '\0')
	{
		v += (int)name[c];
		c++;
	}
	int pos = v%m;
	int t = pos;
	while (hash[pos].isValid && !hash[pos].empty)
	{
		if (strcmp(name, hash[pos].name) == 0)				// 说明同号码查找 
		{
			cout << hash[pos].name << " " << hash[pos].address << " " << hash[pos].num << endl;
			return pos;
		}
		else
			pos = (pos + 1) % m;
		if (pos == t)
		{
			cout << "无此记录" << endl;
			return -1;
		}

	}
	cout << "无此记录" << endl;
	return -1;
}

void del(vector<Node> &hash, int m, char num[12]) //删除用户信息 ,按号码
{
	int c = 3;
	unsigned int v = (int)num[2];			// 强制类型转换 
	while (num[c] != '\0')
	{
		v += (int)num[c];
		c++;
	}
	int pos = v%m;
	int t = pos;
	while (hash[pos].isValid && !hash[pos].empty)		// 意义同查找操作
	{
		if (strcmp(num, hash[pos].num) == 0)
		{
			hash[pos].isValid = false;				// 使此位置无效且为空来删除此节点 
			hash[pos].empty = true;
			cout << "成功删除" << endl;
			return;
		}
		else
			pos = (pos + 1) % m;
		if (pos == t || hash[pos].empty)				//  若查找一圈后找不到此信息或者找到空位置依旧无此记录 
		{
			cout << "无此记录" << endl;
			return ;
		}

	}
	cout << "无此记录" << endl;	
	return;
}

void del2(vector<Node> &hash, int m, char name[8]) //删除用户信息 ,按姓名
{
	int c = 1;
	unsigned int v = (int)name[0];
	while (name[c] != '\0')
	{
		v += (int)name[c];
		c++;
	}
	int pos = v%m;
	int t = pos;
	while (hash[pos].isValid && !hash[pos].empty)		// 意义同查找操作 
	{
		if (strcmp(name, hash[pos].name) == 0)
		{
			hash[pos].isValid = false;				// 使此位置无效且为空来删除此节点 
			hash[pos].empty = true;
			cout << "成功删除" << endl;
			return;
		}
		else
			pos = (pos + 1) % m;
		if (pos == t || hash[pos].empty)		//  若查找一圈后找不到此信息或者找到空位置依旧无此记录 
		{
			cout << "无此记录" << endl;
			return;
		}

	}
	cout << "无此记录" << endl;
	return;
}

void menu() //菜单 
{
	cout << endl;
	cout << endl;
	cout << "		★★~~~~~~~~~~~~~~~通讯录~~~~~~~~~~~~~~~~~~~★★\n" << endl;
	cout << "		★◆----------------------------------------◆★\n" << endl;
	cout << "		★｜		 0.请添加联系人记录         ｜★\n" << endl;
	cout << "		★｜		 1.查找联系人记录           ｜★\n" << endl;
	cout << "		★｜		 2.联系人姓名散列           ｜★\n" << endl;
	cout << "		★｜		 3.联系人号码散列           ｜★\n" << endl;
	cout << "		★｜		 4.删除联系人记录           ｜★\n" << endl;
	cout << "		★｜		 5.保存到指定文件夹         ｜★\n" << endl;
	cout << "		★｜		 6.计算哈希表平均查找长度   ｜★\n" << endl;
	cout << "		★｜		 7.退出系统                 ｜★\n" << endl;
	cout << "		★◆----------------------------------------◆★\n" << endl;
	cout << "		★★★★★★★★★★★★★★★★★★★★★★★★\n" << endl;

}

bool IsPrime(int m)//判断素数
{
	for (int i = 2; i <= sqrt(m); i++)
		if (m%i == 0)
			return false;
	return true;
}



void list(vector<Node> &hash) //显示列表
{
	int i;
	int count = 0;
	for (i = 0; i<hash.size(); i++)
	{		
		if(hash[i].isValid&&hash[i].empty!=true)		// 哈希表有效且不为空 
		{
			cout << hash[i].name << " " << hash[i].address << " " << hash[i].num << endl;
			count++;			// 	计数 
		}		
	}
	cout << "当前联系人数量：" << count << endl;
}

int load(Node * a) //从文件加载用户信息 
{
	ifstream fin("save.txt", ios::in);
	if (!fin)
	{
		cout << "Can't open the file!" << endl;
		exit(0);
	}	
	int i = 0;
	while (!fin.eof())
	{
		fin >> a[i].name >> a[i].address >> a[i].num;
		i++;
	}
	return i;
}

void save(vector<Node> &hash) //保存用户信息 
{
	int i;
	fstream iiout("save.txt", ios::out);
	if (hash[0].isValid && !hash[0].empty)
	{
		iiout << hash[0].name << " " << hash[0].address << " " << hash[0].num ;
	}
	for (i = 1; i<hash.size(); i++)
	{
		if (hash[i].isValid && !hash[i].empty)
		{
			iiout <<endl<< hash[i].name << " " << hash[i].address << " " << hash[i].num;			// 因为空行也被误算为一个联系人，所以分为两个 
		}
	}
}

float cal(vector<Node> &hash)			// 计算平均查找长度 
{
	int i;
	float total = 0.0;
	int count = 0;
	for (i = 0; i<hash.size(); i++)
	{
		if (hash[i].isValid && !hash[i].empty)
		{			
			total+=hash[i].conftimes;
			count++;
		}
	}
	return total / count;
}

Node input() //输入节点 
{
	Node p;
	cout << "输入姓名：" << endl;
	cin >> p.name;
	cout << "输入地址：" << endl;
	cin >> p.address;
	cout << "输入电话：" << endl;
	cin >> p.num;
	return p;
}

int add(vector<Node> &hash1, vector<Node> &hash2, int m) //添加节点 （添加新的联系人到号码哈希表和姓名哈希表）
{
	Node p;
	p = input();		// 输入节点 
	int i;
	for (i = 0; i<hash1.size(); i++)
	{
		if ( hash1[i].empty)
		{
			break;
		}
	}
	if (i == hash1.size())
	{
		cout << "号码哈希表已满，无法插入！"<<endl;
	}
	else
	{
		int c = 3;
		unsigned int v = (int)p.num[2];		//强制转换数据类型 
		while (p.num[c] != '\0')
		{
			v += (int)p.num[c];
			c++;
		}
		int H = v % m;//hash函数为Hash(key)=key%p,p=m
		int ct = 1;
		while (!hash1[H].empty)//线性探测法处理冲突
		{
			H = (H + 1) % m;
			ct++;
		}
		hash1[H] = p;
		hash1[H].empty = false;
		hash1[H].conftimes = ct;
		hash1[H].isValid = true;

		cout << "往号码哈希表添加成功!" << endl;
	}

	int j;
	for (j = 0; j<hash2.size(); j++)
	{
		if (hash2[j].empty)
		{
			break;
		}
	}
	if (j == hash2.size())
	{
		cout << "姓名哈希表已满，无法插入！" << endl;
	}
	else
	{
		int c = 1;
		unsigned int v = (int)p.name[0];		// 强制转换数据类型 
		while (p.name[c] != '\0')
		{
			v += (int)p.name[c];
			c++;
		}
		int H = v % m;//hash函数为Hash(key)=key%p,p=m
		int ct = 1;
		while (!hash2[H].empty)//线性探测法处理冲突
		{
			H = (H + 1) % m;
			ct++;
		}
		hash2[H] = p;
		hash2[H].empty = false;
		hash2[H].conftimes = ct;
		hash2[H].isValid = true;

		cout << "往姓名哈希表添加成功!" << endl;
	}

	return 0;
}

int main()
{	
	cout << "正在载入初始数据......"<<endl;
	char num[11];
	char name[8];

	Node a[MAX];
	
	int n = load(a);		// 得到数据个数 
	int m = n+1;                // 防止n为素数直接无法在插入
	while (!IsPrime(m))//取表长m为大于等于n的最小素数,用来减少冲突 （因为素数的因数只有1和它本身，所以可以减少冲突） 
		m++;
	vector<Node> hash1;
	vector<Node> hash2;
	Gethash1(hash1, a, m, n);
	Gethash2(hash2, a, m, n);

	int sel;
	while (1)
	{
		menu();
		cout << "请选择功能：";
		cin >>sel;
		if (sel == 1)
		{
			cout <<"------------------" << endl;
			cout <<"| 1.按号码查询   |" << endl;
			cout <<"| 2.按姓名查询   |" << endl;
			cout <<"------------------"	<< endl;
			int b;
			cin >> b;
			if (b == 1)
			{
				cout << "请输入电话号码:" << endl;
				cin >> num;
				cout << "输出查找的信息:" << endl;
				HashSearch1(hash1, m, num);
			}
			else
			{
				cout << "请输入姓名:" << endl;
				cin >> name;
				cout << "输出查找的信息:" << endl;
				HashSearch2(hash2, m, name);
			}
		}
		if (sel == 2)
		{
			cout << "姓名散列结果:" << endl;
			list(hash2);
		}
		if (sel == 0)
		{
			cout << "请输入要添加的内容:" << endl;
			add(hash1, hash2,m);
		}
		if (sel == 3)
		{
			cout << "号码散列结果:" << endl;
			list(hash1);
		}
		if (sel == 4)
		{
			cout <<"------------------" << endl;
			cout <<"| 1.按号码删除   |" << endl;
			cout <<"| 2.按姓名删除   |" << endl;
			cout <<"------------------"	<< endl;
			int b;
			cin >> b;
			if (b ==1)
			{
				cout << "请输入电话号码:" << endl;
				cin >> num;
				del(hash1, m, num);	
			}
			else
			{
				cout << "请输入姓名:" << endl;
				cin >> name;
				del2(hash2, m, name);
			}
			
		}
		if (sel == 5)
		{
			cout << "通信录已保存:" << endl;
			save(hash1);
		}
		if (sel == 6)
		{		
			cout <<"------------------" << endl;
			cout <<"| 1.号码哈希表  |" << endl;
			cout <<"| 2.姓名哈希表   |" << endl;
			cout <<"------------------"	<< endl;
			int b;
			cin >> b;
			if (b == 1)
			{
				cout << "平均查找长度为:" << cal(hash1) << endl;
			}
			else
			{
				cout << "平均查找长度为:" << cal(hash2) << endl;
			}
		}
		if (sel == 7)
		{
			exit(0);
		}
	}
	return 0;

}
